﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Insertion_Sort
{
    public static class InsertionSort
    {
        private static int[] array;

        public static int[] Sort(int[] arr)
        {
            array = arr;
            InsertionSortHelper();

            return array;
        }

        private static void InsertionSortHelper()
        {
            for (int next = 1; next < array.Length; next++)
            {
                int insert = array[next];
                int moveItem = next;

                while (moveItem > 0 && array[moveItem - 1] > insert)
                {
                    array[moveItem] = array[moveItem - 1];
                    --moveItem;
                }

                array[moveItem] = insert;
            }
        }
    }
}
